/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/11
 * \* Time: 10:25
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 丑数 {
    public int nthUglyNumber(int n) {
        //使用dp数组来存储丑数序列
        int[] dp=new int[n];
        dp[0]=1;
        // 下个应该通过乘2来获得新丑数的数据是第a个， 同理b, c
        int a=0,b=0,c=0;

        for(int i=1;i<n;i++){
            // 第a丑数个数需要通过乘2来得到下个丑数，第b丑数个数需要通过乘2来得到下个丑数，同理第c个数
            int n2=dp[a]*2,n3=dp[b]*3,n5=dp[c]*5;
            dp[i]=Math.min(n2,Math.min(n3,n5));
            if(dp[i] == n2){
                a++; // 第a个数已经通过乘2得到了一个新的丑数，那下个需要通过乘2得到一个新的丑数的数应该是第(a+1)个数
            }
            if(dp[i] == n3){
                b++; // 第 b个数已经通过乘3得到了一个新的丑数，那下个需要通过乘3得到一个新的丑数的数应该是第(b+1)个数
            }
            if(dp[i] == n5){
                c++; // 第 c个数已经通过乘5得到了一个新的丑数，那下个需要通过乘5得到一个新的丑数的数应该是第(c+1)个数
            }
        }
        //返回最后一个丑数
        return dp[n-1];
    }
}